package org.xiaoxin.leetcode.array;

import java.util.Arrays;

/**
 * 283. 移动零
 * <p>
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 * <p>
 * 请注意，必须在不复制数组的情况下原地对数组进行操作。
 * <p>
 * 示例 1:
 * 输入: nums = [0,1,0,3,12]
 * 输出: [1,3,12,0,0]
 * <p>
 * 示例 2:
 * 输入: nums = [0]
 * 输出: [0]
 * <p>
 * 提示：
 * 1 <= nums.length <= 10^4
 * -2^31 <= nums[i] <= 2^31 - 1
 * <p>
 * 进阶：你能尽量减少完成的操作次数吗？
 * <p>
 * 难度：简单
 * 标签：数组、双指针
 *
 * @author xiaoxin
 */
public class _283_moveZeroes {

    /**
     * 方法一：双指针法（推荐）
     * 思路：使用双指针，一个指针指向非零元素的位置，另一个指针遍历数组
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     * <p>
     */
    public void moveZeroes(int[] nums) {
        // 提示：
        // 1. 使用两个指针：left 指向下一个非零元素应该放置的位置，right 遍历数组
        // 2. 当 right 指向非零元素时，将其与 left 位置的元素交换，然后 left++
        // 3. right 继续向前遍历
        int left = 0;
        int right = 0;
        int n = nums.length;
        while (right < n) {
            if (nums[right] != 0) {
                // 同步推进时，原地交换比判断 left != right 更快。
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
            }
            right++;
        }

    }

    /**
     * 方法二：两次遍历法
     * 思路：第一次遍历将非零元素前移，第二次遍历将剩余位置填充为0
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     * <p>
     */
    public void moveZeroes2(int[] nums) {
        // 提示：
        // 1. 第一次遍历：将所有非零元素移动到数组前面
        // 2. 第二次遍历：将剩余位置全部填充为0
        int current = 0;
        for (int num : nums) {
            if (num != 0) {
                nums[current++] = num;
            }
        }
        for (int i = current; i < nums.length; i++) {
            nums[i] = 0;
        }
    }


    public static void main(String[] args) {
        testAllMethods();
    }

    /**
     * 测试所有方法
     */
    private static void testAllMethods() {
        System.out.println("=== 283. 移动零 - 测试用例 ===\n");

        // 示例 1
        int[] nums1 = {0, 1, 0, 3, 12};
        testCase("示例 1", nums1, new int[]{1, 3, 12, 0, 0});

        // 示例 2
        int[] nums2 = {0};
        testCase("示例 2", nums2, new int[]{0});

        // 额外测试用例

        // 测试用例 3：全为非零
        int[] nums3 = {1, 2, 3, 4, 5};
        testCase("测试用例 3（全为非零）", nums3, new int[]{1, 2, 3, 4, 5});

        // 测试用例 4：全为零
        int[] nums4 = {0, 0, 0, 0};
        testCase("测试用例 4（全为零）", nums4, new int[]{0, 0, 0, 0});

        // 测试用例 5：零在开头
        int[] nums5 = {0, 0, 1, 2, 3};
        testCase("测试用例 5（零在开头）", nums5, new int[]{1, 2, 3, 0, 0});

        // 测试用例 6：零在末尾
        int[] nums6 = {1, 2, 3, 0, 0};
        testCase("测试用例 6（零在末尾）", nums6, new int[]{1, 2, 3, 0, 0});

        // 测试用例 7：交替排列
        int[] nums7 = {0, 1, 0, 2, 0, 3};
        testCase("测试用例 7（交替排列）", nums7, new int[]{1, 2, 3, 0, 0, 0});

        // 测试用例 8：单个非零元素
        int[] nums8 = {1};
        testCase("测试用例 8（单个非零元素）", nums8, new int[]{1});

        // 测试用例 9：包含负数
        int[] nums9 = {-1, 0, 3, 0, -2};
        testCase("测试用例 9（包含负数）", nums9, new int[]{-1, 3, -2, 0, 0});
    }

    /**
     * 测试单个用例
     */
    private static void testCase(String testName, int[] nums, int[] expected) {
        System.out.println(testName + ":");
        System.out.println("原始数组: " + Arrays.toString(nums));
        System.out.println("期望结果: " + Arrays.toString(expected));

        _283_moveZeroes solution = new _283_moveZeroes();

        // 测试方法一
        int[] nums1 = nums.clone();
        solution.moveZeroes(nums1);
        boolean method1Correct = Arrays.equals(nums1, expected);
        System.out.println("方法一结果: " + Arrays.toString(nums1) + " " +
                (method1Correct ? "✅" : "❌"));

        // 测试方法二
        int[] nums2 = nums.clone();
        solution.moveZeroes2(nums2);
        boolean method2Correct = Arrays.equals(nums2, expected);
        System.out.println("方法二结果: " + Arrays.toString(nums2) + " " +
                (method2Correct ? "✅" : "❌"));


        boolean allCorrect = method1Correct && method2Correct;
        System.out.println("整体测试: " + (allCorrect ? "✅ 通过" : "❌ 失败"));
        System.out.println();
    }
}